#include<bits/stdc++.h>
using namespace std;
#define gc getchar
#define pc putchar
#define pb push_back
#define mp make_pair
#define ls (id<<1)
#define rs ((id<<1)|1)
#define mid ((l+r)>>1)
#define int long long
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)

int read(){
    int ret=0,f=0; char ch=gc();
    while(ch<'0'||ch>'9') f|=(ch=='-'),ch=gc();
    while(ch>='0'&&ch<='9') ret=(ret<<1)+(ret<<3)+(ch^48),ch=gc();
    return f?-ret:ret;
}

void write(int x){
    if(!x) return pc('0'),void();
    if(x<0) pc('-'),x=-x;
    int stk[30],tp=0;
    while(x) stk[++tp]=x%10,x/=10;
    while(tp) pc('0'+stk[tp--]);
    return;
}

const int Maxn=4e6+10;
int P,T,N,M,inv2,Mx,f[3][Maxn];

int Power(int x,int d,int r=1){
    while(d){if(d&1) (r*=x)%=P; (x*=x)%=P,d>>=1;}
    return r;
}

void Solve(){
    memset(f,0,sizeof f);
    N=read(),M=read(),Mx=N*M;
    For(i,0,M) f[0][i]=1; int c=0;
    For(i,2,N){
        Rof(k,Mx,0) Rof(j,M,0)
            (f[c^1][k+j]+=f[c][k])%=P;
        For(k,0,Mx) f[c][k]=0;
        c^=1;
    }
    // For(i,0,Mx) cout<<"i="<<i<<" "<<f[c][i]<<"\n";
    int eq=0;
    For(i,0,Mx) (eq+=f[c][i]*f[c][i]%P)%=P;
    int t=Power(M+1,N*2),inv=Power(t,P-2);
    int ans=(t-eq%P+P)%P*inv2%P*inv%P;
    write(ans),pc('\n');
}

signed main(){
    freopen("pr.in","r",stdin);
    freopen("pr.out","w",stdout);
    P=read(),T=read(),inv2=(P+1)/2; while(T--) Solve();
    return 0;
}